package name.huzhenbo.java.algorithm.talent.twentyfour;

import java.util.*;

class TwentyFourUtils {

    public static <V> Set<List<V>> repeatableCombine(V[] target, final int count) {
        Set<List<V>> result = new HashSet<List<V>>();
        if (count <= 0 || count > target.length) {
            throw new IllegalArgumentException("Count should be bigger than 0 and smaller than target's length.");
        }

        int[] sequenceHolder = new int[count];
        while (true) {
            List<V> combine = new ArrayList<V>();
            for (int j = 0; j < count; j++) {
                combine.add(target[sequenceHolder[j]]);
            }
            result.add(combine);
            boolean changed = false;
            for (int j = count - 1; j >= 0; j--) {
                if (sequenceHolder[j] < target.length - 1) {
                    changed = true;
                    sequenceHolder[j] = sequenceHolder[j] + 1;
                    for (int i = j; i < count; i++) {
                        sequenceHolder[i] = sequenceHolder[j];
                    }
                    break;
                }
            }
            if (!changed) {
                break;
            }
        }
        return result;
    }

    public static <V> Set<List<V>> permutate(V[] target) {
        return permutate(target, 0);
    }

    public static <V> Set<List<V>> combine(V[] target, final int count) {
        if (count > target.length) {
            throw new IllegalArgumentException("The count should not be more than the length of target.");
        }
        return combine(target, target.length, count, new int[count], count);
    }

    private static <V> Set<List<V>> combine(V[] target, int currentLength, int currentCount, int[] sequenceHolder, final int count) {
        Set<List<V>> result = new HashSet<List<V>>();
        for (int i = currentLength; i >= currentCount; i--) {
            sequenceHolder[currentCount - 1] = i - 1;
            if (currentCount > 1) {
                result.addAll(combine(target, i - 1, currentCount - 1, sequenceHolder, count));
            } else {
                List<V> found = new ArrayList<V>();
                for (int j = 0; j < count; j++) {
                    found.add(target[sequenceHolder[j]]);
                }
                result.add(found);
            }
        }
        return result;
    }

    private static <V> Set<List<V>> permutate(V[] target, int currentIndex) {
        final int count = target.length;
        Set<List<V>> result = new HashSet<List<V>>();
        if (currentIndex == count - 1) {
            result.add(Arrays.asList(target.clone()));
        } else {
            for (int i = currentIndex; i < count; i++) {
                swap(target, currentIndex, i);
                result.addAll(permutate(target, currentIndex + 1));
                swap(target, currentIndex, i);
            }
        }
        return result;
    }

    private static <V> void swap(V[] target, int k, int i) {
        V temp = target[k];
        target[k] = target[i];
        target[i] = temp;
    }
}